Как показано на рис. 4.10, в, для воспроизводства случайным образом выбираются две пары в соответствии с вероятностями, показанными на рис. 4.10, б. Обратите внимание на то, что один индивидуум выбирается дважды, а один вообще остается не выбранным11. Для каждой пары, предназначенной для воспроизводства, среди позиций в строке случайным образом выбирается точка скрещивания. На рис. 4.10 точки скрещивания находятся после третьей цифры в первой паре и после пятой цифры во второй паре.

Как показано на рис. 4.10, г, сами потомки создаются путем перекрестного обмена подстроками родительских строк, разорванных в точке скрещивания. Например, первый потомок первой пары получает три первые цифры от первого родителя, а остальные цифры — от второго родителя, тогда как второй потомок получает первые три цифры от второго родителя, а остальные — от первого родителя. Состояния задачи с восемью ферзями, участвующие в этом этапе воспроизводства, показаны на рис. 4.11. Данный пример иллюстрирует тот факт, что если два родительских состояния являются весьма различными, то операция скрещивания способна выработать состояние, которое намного отличается и от одного, и от. другого родительского состояния. Часто происходит так, что популяция становится весьма разнообразной на самых ранних этапах этого процесса, поэтому скрещивание (как и эмуляция отжига) в основном обеспечивает выполнение крупных этапов в пространстве состояний в начале процесса поиска и более мелких этапов позднее, когда большинство индивидуумов становятся весьма похожими друг на друга.

Наконец, на рис. 4.10, д показано, что каждое местонахождение подвергается случайной мутации с небольшой независимой вероятностью. В первом, третьем и четвертом потомках мутация свелась к изменению одной цифры. В задаче с восемью ферзями эта операция соответствует выбору случайным образом одного ферзя и перемещению этого ферзя на случайно выбранную клетку в его столбце. В листинге 4.4 приведен алгоритм, который реализует все эти этапы.

Рис. 4. 11 Состояния задачи с восемью ферзями, соответствующие первым двум родительским состояниям, показанным на рис. 4.10, в, и первому потомку, показанному на рис. 4.10. г. Затененные столбцы на этапе скрещивания теряются, а незатененные сохраняются